package Dict;

public class Dict {
    private final DictHT[] ht; // 两个哈希表
    private int rehashidx; // 一次 rehash 进度指针，-1 表示没有进行 rehash

    public Dict(int size) {
        ht = new DictHT[2]; // 创建两个哈希表
        ht[0] = new DictHT(size); // 当前hash表
        ht[1] = new DictHT(0); // 临时hash表
        rehashidx = -1;
    }

    // 插入
    public void insert(String key, Object value) {
        // 正在进行rehash操作时，会直接将元素插入到ht[1]中
        if (rehashidx == -1) ht[0].insert(key, value);
        else ht[1].insert(key, value);

        // 如果当前哈希表的元素数超过 75% 时，进行渐进式 rehash
        if (ht[0].getUsed() >= ht[0].getSize() * 0.75) rehash(1);
    }

    // 渐进式rehash，每次rehash barrelage个桶
    public void rehash(int barrelage) {
        if (rehashidx == -1) {
            rehashidx = 0;

            // ht[1]的长度是大于等于ht[0]的used+1的最小2的幂
            int newSize = ht[0].getUsed() + 1;
            int newTableSize = 1;
            while (newTableSize < newSize) newTableSize *= 2;
            ht[1] = new DictHT(newTableSize);
        }

        while(barrelage-- > 0) {
            if (ht[0].getSize() <= rehashidx) break;

            // 如果当前桶为空，递增rehashidx
            while(ht[0].getTable()[rehashidx] == null) {
                rehashidx++;
            }

            // 遍历当前桶中的链表
            DictEntry entry = ht[0].getTable()[rehashidx];
            while (entry != null) {
                // 保存当前entry下一个节点的引用，将当前元素移到ht[1]时，不丢失当前entry下一个节点的引用
                DictEntry nextEntry = entry.next;

                // 计算当前entry在ht[1]中的索引
                int index = ht[1].hashIndex(entry.getKey());

                // 将元素从ht[0]迁移到ht[1]中（头插法）
                entry.next = ht[1].getTable()[index];
                ht[1].getTable()[index] = entry;

                ht[0].setUsed(ht[0].getUsed() - 1);
                ht[1].setUsed(ht[1].getUsed() + 1);

                // 向下移动工作指针，开启链表下一个节点
                entry = nextEntry;
            }

            ht[0].getTable()[rehashidx] = null; // 清空当前桶
            rehashidx++; // 迁移到下一个桶
        }

        // 检查是否已经完成全表的rehash，如果完全，则rehashidx = -1
        if (ht[0].getUsed() == 0) {
            // 扩容ht[0]
            ht[0] = new DictHT(ht[1].getSize());

            // 将ht[1]的表赋值给ht[0]
            ht[0] = ht[1];

            // 重置ht[1]
            ht[1] = new DictHT(0);

            // 重置rehash索引,表示rehash结束
            rehashidx = -1;
        }
    }

    // 查找
    public String find(String key) {
        return ht[0].find(key) != null ? ht[0].find(key) : ht[1].find(key);
    }

    // 获取Dict中全部元素
    public DictEntry[] getAllData() {
        DictEntry[] allData = new DictEntry[ht[0].getUsed() + ht[1].getUsed()];
        int dictEntryIndex = 0;
        for (int i = 0; i < ht[0].getSize(); i++) {
            // 第i个桶的链表
            DictEntry workEntry = ht[0].getTable()[i];
            while (workEntry != null) {
                allData[dictEntryIndex++] = workEntry;
                workEntry = workEntry.next;
            }
        }
        for (int i = 0; i < ht[1].getSize(); i++) {
            // 第i个桶的链表
            DictEntry workEntry = ht[1].getTable()[i];
            while (workEntry != null) {
                allData[dictEntryIndex++] = workEntry;
                workEntry = workEntry.next;
            }
        }
        return allData;
    }
}
